package de.fhkl.imst.i.cgma.raytracer;

import java.awt.Color;
import java.awt.Rectangle;
import java.io.File;
import java.io.IOException;
import java.util.Random;
import java.util.Vector;

import de.fhkl.imst.i.cgma.raytracer.file.*;
import de.fhkl.imst.i.cgma.raytracer.gui.*;

public class Raytracer05_ShadingAA_OBJ implements IRayTracerImplementation 
{
	
    // viewing volume with infinite end
    private float fovyDegree;
    private float near;
    private float fovyRadians;
    
    // one hardcoded point light as a minimal solution :-(
    private float[] Ia = { 0.25f, 0.25f, 0.25f }; // ambient light color
    private float[] Ids = { 1.0f, 1.0f, 1.0f }; // diffuse and specular light color
    private float[] ICenter = { 3.0f, -4.0f, 2.0f }; // center of point light
    
    //private float[] ICenter = { 4.0f, 4.0f, 2.0f }; // center of point light
    
    private float rayEx, rayEy, rayEz;    // eye point==ray starting point
    
	RayTracerGui gui = new RayTracerGui(this);
	
	private int resx, resy;        // viewport resolution
	private float h, w, aspect;   // window height, width and aspect ratio
	
	final int difuseIndex = 3;
	final int ambientIndex = 0;
	final int specularIndex = 6;
	
	final boolean useAA = false;
	final int AAFactor = 2;
	
	Vector<RT_Object> objects;
	
	public void rayTraceThread(int start, int numThreads)
	{
		// FAKE ;)
	}
	
	private Raytracer05_ShadingAA_OBJ() 
	{
		try 
		{
		    //gui.addObject(RTFileReader.read(I_Sphere.class, new File("data/ikugel.dat")));
			gui.addObject(RTFileReader.read(T_Mesh.class, new File("data/kugel2.dat")));
			gui.addObject(RTFileReader.read(T_Mesh.class, new File("data/kugel1.dat")));
			gui.addObject(RTFileReader.read(T_Mesh.class, new File("data/kugel3.dat")));
		    //gui.addObject(RTFileReader.read(T_Mesh.class, new File("data/quader.dat")));
			
			//gui.addObject( OBJFileReader.readFile(new File("data/boy.obj")) );
		    
		    objects = gui.getObjects();
		} 
		catch (Exception e) 
		{
		    e.printStackTrace();
		}
	}
	
	public void setViewParameters(float fovyDegree, float near)
	{
	    // set attributes fovyDegree, fovyRadians, near
		this.fovyDegree = fovyDegree;
		this.near = near;
		this.fovyRadians = (float) (fovyDegree / 180.0f * Math.PI);
			
	    // set attributes resx, resy, aspect
	    resx = gui.getResX();
	    resy = gui.getResY();
	    aspect = (float) resx / (float) resy;

	    // set attributes h, w
	    h = (float) (2 * near * Math.tan(fovyRadians / 2));
	    w = h * aspect; 
	}
	
	@Override
	public void doRayTrace() 
	{
	    float x, y, z;                // intersection point in viewing plane
	    float rayVx, rayVy, rayVz;    // ray vector
	    Color color;
	    
	    // hardcoded viewing volume with fovy and near 
	    setViewParameters(90.0f, 1.0f);
	    	
	    // set eye point
	    rayEx = 0.0f;
	    rayEy = -5.5f;
	    rayEz = 2.0f;
	   
	    // set eye point
	    rayEx = 0.0f;
	    rayEy = 0.0f;
	    rayEz = 0.0f;
	    
	    // D'OH z = -1 * near;
	    z = rayEz - near;
	    
	    final float AASubPixel = 1.0f / AAFactor;
	    final float AAHalf = 2 * AASubPixel;
	    
	    final int SubPixCount = AAFactor * AAFactor;
	    
	    int sumR = 0, sumG = 0, sumB = 0;
	    float traceX, traceY;   

	    // DEBUGING
	    //resx=resy=1;
	    
	    //System.out.println("Start prepare Mesh");
	    prepareMeshData();
	    //System.out.println("End prepare Mesh");
	    
	    RenderThread threads[] = new RenderThread[4];
	    
	    threads[0] = new RenderThread(new Rectangle(0, 0, resx / 2, resy / 2), this);
	    threads[1] = new RenderThread(new Rectangle(resx / 2, 0, resx, resy / 2), this);
	    
	    threads[2] = new RenderThread(new Rectangle(0, resy / 2, resx / 2, resy), this);
	    threads[3] = new RenderThread(new Rectangle(resx / 2, resy / 2, resx, resy), this);
	    
	    Thread threads2[] = new Thread[4];
	    
	    threads2[0] = new Thread(threads[0]);
	    threads2[1] = new Thread(threads[1]);
	    threads2[2] = new Thread(threads[2]);
	    threads2[3] = new Thread(threads[3]);
	    
	    threads2[0].start();
	    threads2[1].start();
	    threads2[2].start();
	    threads2[3].start();
	    
	    rayTraceArea(new Rectangle(0, 0, resx, resy));
	}
	
	public void rayTraceArea(Rectangle area)
	{
	    float x, y, z;                // intersection point in viewing plane
	    float rayVx, rayVy, rayVz;    // ray vector
	    Color color;
	   
	    z = rayEz - near;
	    
	    final float AASubPixel = 1.0f / AAFactor;
	    final float AAHalf = 2 * AASubPixel;
	    
	    final int SubPixCount = AAFactor * AAFactor;
	    
	    int sumR = 0, sumG = 0, sumB = 0;
	    float traceX, traceY;  
		
		int width = area.width;
		int height = area.height;
		
		// xp, yp: pixel coordinates 
		for(int xp = area.x; xp < width; ++xp) 
		{
			for(int yp = area.y; yp < height; ++yp) 
			{	

			    if (useAA)
			    {
				    sumR = 0;
				    sumG = 0;
				    sumB = 0;
				    
				    rayVz = z - rayEz;
				    
				    for (int ax = 0; ax < AAFactor; ax++)
				    {
				    	for (int ay = 0; ay < AAFactor; ay++)
				    	{
				    		traceX = (xp - AAHalf) + ax * AASubPixel;
				    		traceY = (yp - AAHalf) + ay * AASubPixel;
				    		
							
						    // x, y: view coordinates
						    x = (float) (traceX) / (resx - 1) * w - ( (float) w / 2.0f);
						    y = (float) ((resy) - 1.0d - traceY) / (resy) * h - ( (float) h/ 2.0f);
				    		
						    // ray vector
						    rayVx = x - rayEx;
						    rayVy = y - rayEy;
						    
						   				    
						    // get color or null along the ray
						    color = traceRayAndGetColor(rayEx, rayEy, rayEz, rayVx, rayVy, rayVz);
						    
						    // if color!=null set pixel with color
						    if (color != null)
						    {
						    	sumR += color.getRed();
						    	sumG += color.getGreen();
						    	sumB += color.getBlue();
						    	//gui.setPixel(xp, yp, color.getRGB());
						    }
				    	}
				    }
				    
				    color = new Color(sumR / SubPixCount, sumG / SubPixCount, sumB / SubPixCount);
				    gui.setPixel(xp, yp, color.getRGB());
			    }
			    else
			    {
			    	
				    // x, y: view coordinates
				    //x = (float) (xp) / (resx - 1) * w - ( (float) w / 2.0f);
				    //y = (float) ((resy) - 1.0d - yp) / (resy) * h - ( (float) h/ 2.0f);
				    
				    x = rayEx + (float) (xp) / (resx - 1) * w - ( (float) w / 2.0f);
				    y = rayEy + (float) ((resy) - 1.0d - yp) / (resy) * h - ( (float) h/ 2.0f);

				    // DEBUGING
				    //x=y=0;			    
	  
				    // ray vector
				    rayVx = x - rayEx;
				    rayVy = y - rayEy;
				    rayVz = z - rayEz;
				   				    
				    // get color or null along the ray
				    color = traceRayAndGetColor(rayEx, rayEy, rayEz, rayVx, rayVy, rayVz);

				    // if color!=null set pixel with color
				    if (color != null)
				    {
				    	gui.setPixel(xp, yp, color.getRGB());
				    }   			    	
			    }
			    
			}
		}
	}
	
	private boolean testBoundingBox(float rayEx, float rayEy, float rayEz, float rayVx, float rayVy, float rayVz, float [] min, float [] max)
	{
		float pen, t;
		float [] ip = new float[3];
		
		// "rayVn" == 0 => parallel to plane / case n = (0, 0, 1) & n = (0, 0, -1)
		// if intersection with yx plane
		if (Math.abs(rayVz) > 1E-5)
		{
			// test front plane
			    pen = (max[2] - rayEz);
				
			    // calculate intersection point with plane along the ray
			    t = pen / rayVz;
		
			    // the intersection point with the plane
	    		// the intersection point s(t) = RayE + t * RayV
	    		ip[0] = rayEx + t * rayVx;
	    		ip[1] = rayEy + t * rayVy;
	    		ip[2] = rayEz + t * rayVz;
	    		
	    		if (ip[0] >= min[0] && ip[0] <= max[0] && ip[1] >= min[1] && ip[1] <= max[1])
	    		{
	    			return true;
	    		}
	    		
    		// test back plane
	    		
	    		pen = - (min[2] - rayEz);	// n = (0, 0, -1) => -
	    		
	    		// calculate intersection point with plane along the ray
			    t = pen / rayVz * -1;
			    
			    // the intersection point with the plane
	    		// the intersection point s(t) = RayE + t * RayV
	    		ip[0] = rayEx + t * rayVx;
	    		ip[1] = rayEy + t * rayVy;
	    		
	    		if (ip[0] >= min[0] && ip[0] <= max[0] && ip[1] >= min[1] && ip[1] <= max[1])
	    		{
	    			return true;
	    		}
		}
			
		// "rayVn" == 0 => parallel to plane / case n = (0, 1, 0) & n = (0, -1, 0)
		// if intersection with xz plane
		if (Math.abs(rayVy) > 1E-5)
		{
			
			// test upper plane		
				pen = (max[1] - rayEy);
				
				// calculate intersection point with plane along the ray
			    t = pen / rayVy;
		
			    // the intersection point with the plane
	    		// the intersection point s(t) = RayE + t * RayV
	    		ip[0] = rayEx + t * rayVx;
	    		ip[2] = rayEz + t * rayVz;

	    		    		
	    		if (ip[0] >= min[0] && ip[0] <= max[0] && ip[2] <= max[2] && ip[2] >= min[2])
	    		{
	    			return true;
	    		}
	    			    		
    		// test lower plane				
				pen = - (min[1] - rayEy);
				
				// calculate intersection point with plane along the ray
				// t = (p - e) * n / rayV * n => n = (0, -1 !, 0)
			    t = pen / rayVy * -1;
		
			    // the intersection point with the plane
	    		// the intersection point s(t) = RayE + t * RayV
	    		ip[0] = rayEx + t * rayVx;
	    		ip[2] = rayEz + t * rayVz;  		
	    		
	    		if (ip[0] >= min[0] && ip[0] <= max[0] && ip[2] <= max[2] && ip[2] >= min[2])
	    		{
	    			return true;
	    		}		
		}
		
		// "rayVn" == 0 => parallel to plane / case n = (-1, 0, 0) & n = (1, 0, 0)
		// if intersection with zy plane
		if (Math.abs(rayVx) > 1E-5)
		{			
			// test left plane
			
				pen = - (min[0] - rayEx);
				
				t = pen / rayVx * -1;
				
				// the intersection point with the plane
	    		// the intersection point s(t) = RayE + t * RayV
	    		ip[1] = rayEy + t * rayVy;  
	    		ip[2] = rayEz + t * rayVz;
	    		
	    		if (ip[1] >= min[1] && ip[1] <= max[1] && ip[2] <= max[2] && ip[2] >= min[2])
	    		{
	    			return true;
	    		}
	    		
	    		
			// test right plane				
				pen = (max[0] - rayEx);
				
				t = pen / rayVx;
				
				// the intersection point with the plane
	    		// the intersection point s(t) = RayE + t * RayV
	    		ip[1] = rayEy + t * rayVy;  
	    		ip[2] = rayEz + t * rayVz;
	    		
	    		if (ip[1] >= min[1] && ip[1] <= max[1] && ip[2] <= max[2] && ip[2] >= min[2])
	    		{
	    			return true;
	    		}
			
		}
		
		
		return false;
	}
	
	private void prepareMeshData()
	{
		RTFile scene;
		T_Mesh mesh;
		int triangleCount;
	
    	for (int objectsNumber = 0; objectsNumber < objects.size(); objectsNumber++) 
    	{
    	    scene = objects.get(objectsNumber);
    	    
    	    if (scene.getHeader() == "TRIANGLE_MESH") 
    	    {
    	    	mesh = (T_Mesh) scene;
    	    	
    	    	triangleCount = mesh.triangles.length;
    	    	int vertexCount = mesh.vertices.length;
    	    	
    	    	mesh.triangleNormals = new float[triangleCount][3];
    	    	mesh.triangleAreas = new float[triangleCount];
    	    	mesh.triangleColors = new float[triangleCount][3];	// RGB?
    			float[] p1, p2, p3;
    			int p1Index, p2Index, p3Index;
    			
    			float[] l = new float[3];
    			float[] v = new float[3];
    			float rayVx, rayVy, rayVz;
    			
    			switch (mesh.fgp)
			    {
			    
				    case 'g':
				    case 'G':
				    	
				    	mesh.vertexNormals = new float[vertexCount][3];
				    	mesh.vertexColors  = new float[vertexCount][3];
				    	break;
				    	
				    case 'p':
				    case 'P':
				    	
				    	mesh.vertexNormals = new float[vertexCount][3];
				    	break;
				    	
			    }
    			
				// loop over all triangles  
				for (int i = 0; i < mesh.triangles.length; i++) 
				{
					p1Index = mesh.triangles[i][0];
					p2Index = mesh.triangles[i][1];
					p3Index = mesh.triangles[i][2];
					
				    // get the three vertices
				    p1 = mesh.vertices[p1Index];				  				    
				    p2 = mesh.vertices[p2Index];
				    p3 = mesh.vertices[p3Index];
				    
				    // calculate normal n and triangle area a
				    mesh.triangleAreas[i] = calculateN(mesh.triangleNormals[i], p1, p2, p3);
				    
				    // precalculate illumination
				    switch (mesh.fgp)
				    {
				    
					    case 'g':
					    case 'G':
					    case 'p':
					    case 'P':
					    	
					    	// prepare vertex normals
					    	mesh.vertexNormals[p1Index][0] += mesh.triangleNormals[i][0];
					    	mesh.vertexNormals[p1Index][1] += mesh.triangleNormals[i][1];
					    	mesh.vertexNormals[p1Index][2] += mesh.triangleNormals[i][2];
					    	
					    	mesh.vertexNormals[p2Index][0] += mesh.triangleNormals[i][0];
					    	mesh.vertexNormals[p2Index][1] += mesh.triangleNormals[i][1];
					    	mesh.vertexNormals[p2Index][2] += mesh.triangleNormals[i][2];
					    	
					    	mesh.vertexNormals[p3Index][0] += mesh.triangleNormals[i][0];
					    	mesh.vertexNormals[p3Index][1] += mesh.triangleNormals[i][1];
					    	mesh.vertexNormals[p3Index][2] += mesh.triangleNormals[i][2];
					    	
				    
					    	break;
					    	
					    case 'f':
					    case 'F':
				    					    	
						    // light vector at the vertex, normalize!
					        l[0] = ICenter[0] - p1[0];
					    	l[1] = ICenter[1] - p1[1];
					    	l[2] = ICenter[2] - p1[2];
					    	
					    	normalize(l);
					    	             
					    	// ray vector
						    rayVx = p1[0] - rayEx;
						    rayVy = p1[1] - rayEy;
						    rayVz = p1[2] - rayEz;
					    	
					    	// viewing vector at intersection point, normalize!
					    	v[0] = -rayVx;
					    	v[1] = -rayVy;
					    	v[2] = -rayVz;
					    	
					    	normalize(v);
					    	
					    	int matIndex = mesh.verticesMat[mesh.triangles[i][0]];

					    	Color color = phongIlluminate(mesh.materials[matIndex], mesh.materialsN[matIndex], l, mesh.triangleNormals[i], v, Ia, Ids);
					    	mesh.triangleColors[i][0] = color.getRed();
					    	mesh.triangleColors[i][1] = color.getGreen();
					    	mesh.triangleColors[i][2] = color.getBlue();
					    	
					    	break;
				    }				   			 
				}
							
				// illuminate vertices
				switch (mesh.fgp)
			    {
			    
				    case 'g':
				    case 'G':
				    case 'p':
				    case 'P':
				    	
				    	// calculate vertex normals
				    	for (int i = 0; i < vertexCount; i++)
				    	{
				    		float normalLength = (float) Math.sqrt(mesh.vertexNormals[i][0] * mesh.vertexNormals[i][0] + mesh.vertexNormals[i][1] * mesh.vertexNormals[i][1] + mesh.vertexNormals[i][2] * mesh.vertexNormals[i][2]);
				    		
				    		normalize(mesh.vertexNormals[i]);
				    		
				    		//mesh.vertexNormals[i][0] = mesh.vertexNormals[i][0] / normalLength;
				    		//mesh.vertexNormals[i][1] = mesh.vertexNormals[i][1] / normalLength;
				    		//mesh.vertexNormals[i][2] = mesh.vertexNormals[i][2] / normalLength;
				    		
				    		if (mesh.fgp == 'p' || mesh.fgp == 'P')
				    			continue;
				    		
				    		// light vector at the vertex, normalize!
					        l[0] = ICenter[0] - mesh.vertices[i][0];
					    	l[1] = ICenter[1] - mesh.vertices[i][1];
					    	l[2] = ICenter[2] - mesh.vertices[i][2];
					    	
					    	normalize(l);
					    	             
					    	// ray vector
						    rayVx = mesh.vertices[i][0] - rayEx;
						    rayVy = mesh.vertices[i][1] - rayEy;
						    rayVz = mesh.vertices[i][2] - rayEz;
					    	
					    	// viewing vector at intersection point, normalize!
					    	v[0] = -rayVx;
					    	v[1] = -rayVy;
					    	v[2] = -rayVz;
					    	
					    	normalize(v);
					    	
					    	int matIndex = mesh.verticesMat[i];

					    	phongIlluminate(mesh.materials[matIndex], mesh.materialsN[matIndex], l, mesh.vertexNormals[i], v, Ia, Ids, mesh.vertexColors[i]);
				    	}			    	
				    	
				    	break;
				    	
			    }
				
				// illuminate vertices
				switch (mesh.fgp)
			    {
			    				  
				    case 'o':
				    	
				    	// loop over all triangles  
						for (int i = 0; i < mesh.triangles.length; i++) 
						{
							p1Index = mesh.triangles[i][0];
							p2Index = mesh.triangles[i][1];
							p3Index = mesh.triangles[i][2];
							
						    // get the three vertices
						    p1 = mesh.vertices[p1Index];
						    p2 = mesh.vertices[p2Index];
						    p3 = mesh.vertices[p3Index];
						    
						    // calculate normal n and triangle area a
						    mesh.triangleAreas[i] = calculateN(mesh.triangleNormals[i], p1, p2, p3);
						}
				    	
				    	mesh.vertexColors  = new float[vertexCount][3];
				    	
				    	// calculate vertex normals
				    	for (int i = 0; i < vertexCount; i++)
				    	{
				    		
				    		// light vector at the vertex, normalize!
					        l[0] = ICenter[0] - mesh.vertices[i][0];
					    	l[1] = ICenter[1] - mesh.vertices[i][1];
					    	l[2] = ICenter[2] - mesh.vertices[i][2];
					    	
					    	normalize(l);
					    	             
					    	// ray vector
						    rayVx = mesh.vertices[i][0] - rayEx;
						    rayVy = mesh.vertices[i][1] - rayEy;
						    rayVz = mesh.vertices[i][2] - rayEz;
					    	
					    	// viewing vector at intersection point, normalize!
					    	v[0] = -rayVx;
					    	v[1] = -rayVy;
					    	v[2] = -rayVz;
					    	
					    	normalize(v);
					    	
					    	int matIndex = mesh.verticesMat[i];

					    	phongIlluminate(mesh.materials[matIndex], mesh.materialsN[matIndex], l, mesh.vertexNormals[i], v, Ia, Ids, mesh.vertexColors[i]);
				    	}
				    	
				    	mesh.fgp = 'g';
				    	
				    	break;
				    	
			    }
				
    	    }
    	    
    	}
	}
	
	// returns Color object or null if no intersection was found
    @SuppressWarnings("unused")
	private Color traceRayAndGetColor(float rayEx, float rayEy, float rayEz, float rayVx, float rayVy, float rayVz) 
    {
        RTFile scene = objects.get(0);
        
    	float minT = Float.MAX_VALUE;
    	int minObjectsIndex = -1;
    	int minTriangleIndex = -1;
    	float[] minIP = new float[3];
    	float[] minN = new float[3];
    	float[] minAi = new float[3];
    	float[] minMaterial = new float[3];
    	float minMaterialN = 1;

    	float[] v = new float[3];
    	float[] l = new float[3];
    	
                
    	// viewing vector at intersection point, normalize!
    	v[0] = -rayVx;
    	v[1] = -rayVy;
    	v[2] = -rayVz;
     
    	normalize(v);
        
        I_Sphere sphere;
        T_Mesh mesh;
        
    	// loop over all scene objects to find the nearest intersection, that
    	// is:
    	// object with number minObjectIndex, if it is a mesh the corresponding
    	// face has the index minIndex
    	// minT is the minimal factor t of the ray equation s(t)=rayE+t*rayV
    	// where the nearest intersection takes place
    	// minMaterial and minMaterialN is the material to use at the nearest
    	// intersection point
    	for (int objectsNumber = 0; objectsNumber < objects.size(); objectsNumber++) 
    	{
    	    scene = objects.get(objectsNumber);
    	    
    	    // object is an implicit sphere?
	        if(scene.getHeader()=="IMPLICIT_SPHERE")
	        {   
	        	sphere = (I_Sphere)scene;
	              	
	            // intersection uses quadratic equation
	        	float emx, emy, emz;
	        	
	        	emx = rayEx - sphere.center[0];
	        	emy = rayEy - sphere.center[1];
	        	emz = rayEz - sphere.center[2];
	        	
	        	float ememScalar = emx * emx + emy * emy + emz * emz;
	        	float vvScalar = rayVx * rayVx + rayVy * rayVy + rayVz * rayVz;
	        	float vemScalar = rayVx * emx + rayVy * emy + rayVz * emz;
	        	
	        	// t*t * vvScalar + 2 * t * vemScalar + ememScalar - sphere.radius * sphere.radius;
	        	
	        	float a, p, q;
	        	
	        	a = vvScalar;
	        	p = (2 * vemScalar) / a;
	        	q = (ememScalar - sphere.radius * sphere.radius) / a;
	        	
	        	float d = p*p - 4*q;
	        	
	    		// no intersection point? => next object
	    		if (d <= 0)
	    		    continue;
	    		
	    		// from here: intersection takes place!
	
	    		// calculate first intersection point with sphere along the ray
	    		// x1/2 = - p / 2 +- sqrt( (p/2)^2 - q )
	    		float p2 = p / 2.0f;
	    		float t1 = (float) (- p2 + Math.sqrt( p2*p2 - q ));
	    		float t2 = (float) (- p2 - Math.sqrt( p2*p2 - q ));
	  	
	    		float t;
	    		
	    		if (t2 > t1)
	    			t = t1;
	    		else
					t = t2;
	    		
	    		// already a closer intersection point? => next object
	    		if (t > minT)
	    			continue;
	    		
	    		// I'm the winner until now!
	    		minT = t;
	    		
	    		minObjectsIndex = objectsNumber;
	    		
	    		// prepare everything for phong shading
	
	    		// the intersection point s(t) = RayE + t * RayV;
	    		minIP[0] = rayEx + t * rayVx;
	    		minIP[1] = rayEy + t * rayVy;
	    		minIP[2] = rayEz + t * rayVz;
	    		
	    		// the normal vector at the intersection point, normalize!
	    		minN[0] = minIP[0] - sphere.center[0];
	    		minN[1] = minIP[1] - sphere.center[1];
	    		minN[2] = minIP[2] - sphere.center[2];
	    		
	    		normalize(minN);
	    		
	    		// the material
	    		minMaterial = sphere.material;
	    		minMaterialN = sphere.materialN;     
	        }
	        // object is a triangle mesh?
		    else if (scene.getHeader() == "TRIANGLE_MESH") 
		    {
				mesh = (T_Mesh) scene;
				
				if (!testBoundingBox(rayEx, rayEy, rayEz, rayVx, rayVy, rayVz, mesh.min, mesh.max))
				{
					continue;
				}				
				
				//return new Color(0.0f, 1.0f, 1.0f); } return null;} return null;
				
				
				
				float t;
				float[] n;
				float[] ip = new float[3];
		
				float rayVn, pen;
				float[] p1, p2, p3;
				float[] ai = new float[3];
		
				// loop over all triangles  
				for (int i = 0; i < mesh.triangles.length; i++) 
				{			
				    // get the three vertices
				    p1 = mesh.vertices[mesh.triangles[i][0]];
				    p2 = mesh.vertices[mesh.triangles[i][1]];
				    p3 = mesh.vertices[mesh.triangles[i][2]];
		
				    // intermediate version
				    // calculate normal n and triangle area a
				    //n = new float[3];
				    //a = calculateN(n, p1, p2, p3);
				    
				    n = mesh.triangleNormals[i];
		
				    // Backface culling: angle between viewing vector and normal > 90 degrees
				    // scalar product > 0
				    rayVn = rayVx * n[0] + rayVy * n[1] + rayVz * n[2];
		
				    // backface? => next triangle
				    if (rayVn >= 0)
				    	continue;
				    
				    // no intersection point? => next triangle
				    // v * n = 0 => ray parallel to plane
				    if (Math.abs(rayVn) < 1E-7)
				    	continue;
		
				    pen = (p1[0] - rayEx) * n[0] + (p1[1] - rayEy) * n[1] + (p1[2] - rayEz) * n[2];
		
				    // calculate intersection point with plane along the ray
				    t = pen / rayVn;
		
				    // already a closer intersection point? => next triangle
				    if (t >= minT)
				    	continue;
		
				    // the intersection point with the plane
		    		// the intersection point s(t) = RayE + t * RayV
		    		ip[0] = rayEx + t * rayVx;
		    		ip[1] = rayEy + t * rayVy;
		    		ip[2] = rayEz + t * rayVz;
		
				    // no intersection point with the triangle? => next
				    // triangle
				    if (!triangleTest(ip, p1, p2, p3, mesh.triangleAreas[i], ai))
				    {
				    	continue;
				    }

				    // from here: t < minT and triangle intersection
				    // This triangle is the winner until now!
		
				    //return new Color (0.0f, 1.0f, 1.0f);
				    
				//}}} return null;}
				    
				
				    
				    minT = t;
				    minObjectsIndex = objectsNumber;
				    minTriangleIndex = i;
				    minAi[0] = ai[0];
				    minAi[1] = ai[1];
				    minAi[2] = ai[2];
				    
				    // prepare everything for shading alternatives
		
				    // the intersection point
				    minIP[0] = ip[0];
				    minIP[1] = ip[1];
				    minIP[2] = ip[2];				  
		
				    switch (mesh.fgp) 
				    {
					    case 'p':
					    case 'P':
					    	
							 // the material is the material of the first triangle point 
							 int matIndex = mesh.verticesMat[mesh.triangles[minTriangleIndex][0]];
							 minMaterial = mesh.materials[matIndex]; 
							 minMaterialN= mesh.materialsN[matIndex];
							
							break;
				    }
				}
		    	
		    } 
		    else
		    {
		    	continue;	// NEXT OBJECT
		    }
    	}
        
    	// no intersection point found => return with no result
    	if (minObjectsIndex == -1)
    	    return null;
    	
    	scene = objects.get(minObjectsIndex);
    	
    	
    	
    	// ------------------------- illuminating / shading of the nearest found object ------------------------- 
    	
    	
        // implicit: only phong shading available => shade=illuminate
    	if (scene.getHeader() == "IMPLICIT_SPHERE")
    	{
    		// light vector at the intersection point, normalize!
            l[0] = ICenter[0] - minIP[0];
        	l[1] = ICenter[1] - minIP[1];
        	l[2] = ICenter[2] - minIP[2];
        	
        	normalize(l);
    		
    	    return phongIlluminate(minMaterial, minMaterialN, l, minN, v, Ia, Ids);
    	}
    	// triangle mesh: flat, gouraud or phong shading according to file data
    	else if (scene.getHeader() == "TRIANGLE_MESH") 
    	{
    		int r, g, b;
    		
    	    mesh = (T_Mesh) scene;
    	        
    	    switch (mesh.fgp) 
    	    {    
	    	    case 'g':
	    	    case 'G':
	    	    case 'p':
    	    	case 'P':
	    	    	
	    	    	float bu, bv, bw;
	    	    	float fr, fg, fb;
	    	    	
	    	    	bu = minAi[0] / mesh.triangleAreas[minTriangleIndex];
	    	    	bv = minAi[1] / mesh.triangleAreas[minTriangleIndex];
	    	    	bw = minAi[2] / mesh.triangleAreas[minTriangleIndex];
	    	    	
	    	    	int p1Index, p2Index, p3Index;
	    	    	
	    	    	p1Index = mesh.triangles[minTriangleIndex][0];
	    	    	p2Index = mesh.triangles[minTriangleIndex][1];
	    	    	p3Index = mesh.triangles[minTriangleIndex][2];
	    	    	
	    	    	switch (mesh.fgp)
	    	    	{
		    	    	case 'g':
		    	    	case 'G':
		    	    		
		    	    		fr = bu * mesh.vertexColors[p3Index][0] + bv * mesh.vertexColors[p1Index][0] + bw * mesh.vertexColors[p2Index][0];
			    	    	fg = bu * mesh.vertexColors[p3Index][1] + bv * mesh.vertexColors[p1Index][1] + bw * mesh.vertexColors[p2Index][1];
			    	    	fb = bu * mesh.vertexColors[p3Index][2] + bv * mesh.vertexColors[p1Index][2] + bw * mesh.vertexColors[p2Index][2];
			    	    	
			    			if (fr > 1)
			    				fr = 1.0f;
			    			if (fg > 1)
			    				fg = 1.0f;
			    			if (fb > 1)
			    				fb = 1.0f;
			    	    	
			    	    	return new Color(fr, fg, fb);
			    	    	
		    	    	case 'p':
		    	    	case 'P':
		    	    		
		    	    		float n [] = new float[3];
		    	    		
		    	    		n[0] = bu * mesh.vertexNormals[p3Index][0] + bv * mesh.vertexNormals[p1Index][0] + bw * mesh.vertexNormals[p2Index][0];
		    	    		n[1] = bu * mesh.vertexNormals[p3Index][1] + bv * mesh.vertexNormals[p1Index][1] + bw * mesh.vertexNormals[p2Index][1];
		    	    		n[2] = bu * mesh.vertexNormals[p3Index][2] + bv * mesh.vertexNormals[p1Index][2] + bw * mesh.vertexNormals[p2Index][2];
		    	    		
		    	    		normalize(n);
		    	    		
		    	    		// light vector at the intersection point, normalize!
		    	            l[0] = ICenter[0] - minIP[0];
		    	        	l[1] = ICenter[1] - minIP[1];
		    	        	l[2] = ICenter[2] - minIP[2];
		    	        	
		    	        	normalize(l);
		    	    		
		    	    	    return phongIlluminate(minMaterial, minMaterialN, l, n, v, Ia, Ids);
	    	    	}
	    	    	
	    	    case 'f':
	    	    case 'F':
	    	    	
	    	    	// flat shading: use the per triangle precalculated color
	    	    	r = (int) mesh.triangleColors[minTriangleIndex][0];
	    	    	g = (int) mesh.triangleColors[minTriangleIndex][1];
    	    		b = (int) mesh.triangleColors[minTriangleIndex][2];
	    	    	    	    	
	    	    	return new Color(r, g, b);
    	    }
    	}
  
        return null;
        
      
        
    }
    
    private float traceRayAndGetMinT(float sx, float sy, float sz, float rayVx, float rayVy, float rayVz)
    {
        RTFile scene = objects.get(0);
        
    	float minT = Float.MAX_VALUE;
    	int minObjectsIndex = -1;
    	int minTriangleIndex = -1;
    	float[] minIP = new float[3];
    	float[] minN = new float[3];
    	float[] minAi = new float[3];
    	float[] minMaterial = new float[3];
    	float minMaterialN = 1;

    	float[] v = new float[3];
    	float[] l = new float[3];    	
    	
    	for (int objectsNumber = 0; objectsNumber < objects.size(); objectsNumber++) 
    	{
    	    scene = objects.get(objectsNumber);
    	    
    	    // object is an implicit sphere?
	        if(scene.getHeader()=="IMPLICIT_SPHERE")
	        {   
	        	I_Sphere sphere = (I_Sphere)scene;
	              	
	            // intersection uses quadratic equation
	        	float emx, emy, emz;
	        	
	        	emx = sx - sphere.center[0];
	        	emy = sy - sphere.center[1];
	        	emz = sz - sphere.center[2];
	        	
	        	float ememScalar = emx * emx + emy * emy + emz * emz;
	        	float vvScalar = rayVx * rayVx + rayVy * rayVy + rayVz * rayVz;
	        	float vemScalar = rayVx * emx + rayVy * emy + rayVz * emz;
	        	
	        	// t*t * vvScalar + 2 * t * vemScalar + ememScalar - sphere.radius * sphere.radius;
	        	
	        	float a, p, q;
	        	
	        	a = vvScalar;
	        	p = (2 * vemScalar) / a;
	        	q = (ememScalar - sphere.radius * sphere.radius) / a;
	        	
	        	float d = p*p - 4*q;
	        	
	    		// no intersection point? => next object
	    		if (d <= 0)
	    		    continue;
	    		
	    		// from here: intersection takes place!
	
	    		// calculate first intersection point with sphere along the ray
	    		// x1/2 = - p / 2 +- sqrt( (p/2)^2 - q )
	    		float p2 = p / 2.0f;
	    		float t1 = (float) (- p2 + Math.sqrt( p2*p2 - q ));
	    		float t2 = (float) (- p2 - Math.sqrt( p2*p2 - q ));
	  	
	    		float t;
	    		
	    		if (t2 > t1)
	    			t = t1;
	    		else
					t = t2;
	    		
	    		// already a closer intersection point? => next object
	    		if (t > minT)
	    			continue;
	    		
	    		// I'm the winner until now!
	    		minT = t;
	    		
	    		minObjectsIndex = objectsNumber;
	    		
	    		// prepare everything for phong shading
	
	    		// the intersection point s(t) = RayE + t * RayV;
	    		minIP[0] = sx + t * rayVx;
	    		minIP[1] = sy + t * rayVy;
	    		minIP[2] = sz + t * rayVz;
	    		
	    		// the normal vector at the intersection point, normalize!
	    		minN[0] = minIP[0] - sphere.center[0];
	    		minN[1] = minIP[1] - sphere.center[1];
	    		minN[2] = minIP[2] - sphere.center[2];
	    		
	    		normalize(minN);
	    		
	    		// the material
	    		minMaterial = sphere.material;
	    		minMaterialN = sphere.materialN;     
	        }
	        // object is a triangle mesh?
		    else if (scene.getHeader() == "TRIANGLE_MESH") 
		    {
				T_Mesh mesh = (T_Mesh) scene;
				
				if (!testBoundingBox(sx, sy, sz, rayVx, rayVy, rayVz, mesh.min, mesh.max))
				{
					continue;
				}				
				
				//return new Color(0.0f, 1.0f, 1.0f); } return null;} return null;
				
								
				float t;
				float[] n;
				float[] ip = new float[3];
		
				float rayVn, pen;
				float[] p1, p2, p3;
				float[] ai = new float[3];
		
				// loop over all triangles  
				for (int i = 0; i < mesh.triangles.length; i++) 
				{			
				    // get the three vertices
				    p1 = mesh.vertices[mesh.triangles[i][0]];
				    p2 = mesh.vertices[mesh.triangles[i][1]];
				    p3 = mesh.vertices[mesh.triangles[i][2]];
		
				    // intermediate version
				    // calculate normal n and triangle area a
				    //n = new float[3];
				    //a = calculateN(n, p1, p2, p3);
				    
				    n = mesh.triangleNormals[i];
		
				    // Backface culling: angle between viewing vector and normal > 90 degrees
				    // scalar product > 0
				    rayVn = rayVx * n[0] + rayVy * n[1] + rayVz * n[2];
		
				    // backface? => next triangle
				    if (rayVn >= 0)
				    	continue;
				    
				    // no intersection point? => next triangle
				    // v * n = 0 => ray parallel to plane
				    if (Math.abs(rayVn) < 1E-7)
				    	continue;
		
				    pen = (p1[0] - sx) * n[0] + (p1[1] - sy) * n[1] + (p1[2] - sz) * n[2];
		
				    // calculate intersection point with plane along the ray
				    t = pen / rayVn;
		
				    // already a closer intersection point? => next triangle
				    if (t >= minT)
				    	continue;
		
				    // the intersection point with the plane
		    		// the intersection point s(t) = RayE + t * RayV
		    		ip[0] = sx + t * rayVx;
		    		ip[1] = sy + t * rayVy;
		    		ip[2] = sz + t * rayVz;
		
				    // no intersection point with the triangle? => next
				    // triangle
				    if (!triangleTest(ip, p1, p2, p3, mesh.triangleAreas[i], ai))
				    {
				    	continue;
				    }

				    // from here: t < minT and triangle intersection
				    // This triangle is the winner until now!
		
				    //return new Color (0.0f, 1.0f, 1.0f);
				    
				//}}} return null;}
				    
				
				    
				    minT = t;
				}
	    
		    }
    	}
    	
    	return minT;
    }
    
    // calculate normalized face normal fn of the triangle p1, p2 and p3
    // the return value is the area of triangle
    // CAUTION: fn is an output parameter; the referenced object will be
    // altered!
    private float calculateN(float[] fn, float[] p1, float[] p2, float[] p3) 
    {
		float ax, ay, az, bx, by, bz;
	
		// a = Vi2-Vi1, b = Vi3-Vi1
		ax = p2[0] - p1[0];
		ay = p2[1] - p1[1];
		az = p2[2] - p1[2];
		
		bx = p3[0] - p1[0];
		by = p3[1] - p1[1];
		bz = p3[2] - p1[2];
		
		// n = a x b
		fn[0] = ay * bz - az * by;
		fn[1] = az * bx - ax * bz;
		fn[2] = ax * by - ay * bx; 
	
		// normalize n, calculate and return area of triangle
		return normalize(fn) / 2;
    }
    
    // calculate triangle test
    // is p (the intersection point with the plane through p1, p2 and p3) inside
    // the triangle p1, p2 and p3?
    // the return value answers this question
    // a is an input parameter - the given area of the triangle p1, p2 and p3
    // ai will be computed to be the areas of the sub-triangles to allow to
    // compute barycentric coordinates of the intersection point p
    // ai[0] is associated with bu (p1p2p) across from p3
    // ai[1] is associated with bv (pp2p3) across from p1
    // ai[2] is associated with bw (p1pp3) across form p2
    // CAUTION: ai is an output parameter; the referenced object will be
    // altered!
    private boolean triangleTest(float[] p, float[] p1, float[] p2, float[] p3, float a, float ai[]) 
    {
		float tmp[] = new float[3];
	
		ai[0] = calculateN(tmp, p1, p2, p);
		ai[1] = calculateN(tmp, p, p2, p3);
		ai[2] = calculateN(tmp, p1, p, p3);
	
		float sum = (ai[0] + ai[1] + ai[2]);
		
		if ( Math.abs(sum - a) <  1E-5)
		    return true;
	
		return false;
    }
    
	// vector normalization
    // CAUTION: vec is an in-/output parameter; the referenced object will be altered!
    private float normalize(float[] vec) 
    {
    	float l = (float) Math.sqrt(vec[0]*vec[0] + vec[1]*vec[1] + vec[2]*vec[2]);

    	vec[0] = vec[0] / l;
    	vec[1] = vec[1] / l;
    	vec[2] = vec[2] / l;
    	
    	return l;
    }
    
    
    private void phongIlluminate(float[] material, float materialN, float[] l, float[] n, float[] v, float[] Ia, float[] Ids, float[] i)
	{
		float ir = 0, ig = 0, ib = 0; // reflected intensity, rgb channels
		float[] r = new float[3]; // reflection vector
		float ln, rv; // scalar products <l,n> and <r,v>
		
		// <l,n>
		ln = l[0] * n[0] + l[1] * n[1] + l[2] * n[2];
		
		// reflection vector r=2*<l,n>*n-l
		r[0] = 2 * ln * n[0] - l[0];
		r[1] = 2 * ln * n[1] - l[1];
		r[2] = 2 * ln * n[2] - l[2];
		
		// <r,v>
		rv = r[0] * v[0] + r[1] * v[1] + r[2] * v[2];
		
		// ambient component, Ia*ra
		ir += Ia[0] * material[ambientIndex];
		ig += Ia[1] * material[ambientIndex+1];
		ib += Ia[2] * material[ambientIndex+2];
		
		// diffuse component, Ids*rd*<l,n>
		if (ln > 0) 
		{
		    ir += Ids[0] * material[difuseIndex] * ln;
		    ig += Ids[1] * material[difuseIndex+1] * ln;
		    ib += Ids[2] * material[difuseIndex+2] * ln;
		}
		
		// specular component, Ids*rs*<r,v>^n
		if (ln > 0 && rv > 0) 
		{
		    float pow = (float) Math.pow(rv, materialN);
		    ir += Ids[0] * material[specularIndex] * pow;
		    ig += Ids[1] * material[specularIndex+1] * pow;
		    ib += Ids[2] * material[specularIndex+2] * pow;
		}
		
		//System.out.println(ir+" "+ig+" "+ib);
		
		if (ir > 1)
			ir = 1.0f;
		if (ig > 1)
			ig = 1.0f;
		if (ib > 1)
			ib = 1.0f;

		i[0] = ir;
		i[1] = ig;
		i[2] = ib;
	}
    
	// calculate phong illumination model with material parameters material and
	// materialN, light vector l, normal vector n, viewing vector v, ambient
	// light Ia, diffuse and specular light Ids
	// return value is a new Color object
	private Color phongIlluminate(float[] material, float materialN, float[] l, float[] n, float[] v, float[] Ia, float[] Ids)
	{
		float ir = 0, ig = 0, ib = 0; // reflected intensity, rgb channels
		float[] r = new float[3]; // reflection vector
		float ln, rv; // scalar products <l,n> and <r,v>
		
		// <l,n>
		ln = l[0] * n[0] + l[1] * n[1] + l[2] * n[2];
		
		// reflection vector r=2*<l,n>*n-l
		r[0] = 2 * ln * n[0] - l[0];
		r[1] = 2 * ln * n[1] - l[1];
		r[2] = 2 * ln * n[2] - l[2];
		
		// <r,v>
		rv = r[0] * v[0] + r[1] * v[1] + r[2] * v[2];
		
		// ambient component, Ia*ra
		ir += Ia[0] * material[ambientIndex];
		ig += Ia[1] * material[ambientIndex+1];
		ib += Ia[2] * material[ambientIndex+2];
		
		// diffuse component, Ids*rd*<l,n>
		if (ln > 0) 
		{
		    ir += Ids[0] * material[difuseIndex] * ln;
		    ig += Ids[1] * material[difuseIndex+1] * ln;
		    ib += Ids[2] * material[difuseIndex+2] * ln;
		}
		
		// specular component, Ids*rs*<r,v>^n
		if (ln > 0 && rv > 0) 
		{
		    float pow = (float) Math.pow(rv, materialN);
		    ir += Ids[0] * material[specularIndex] * pow;
		    ig += Ids[1] * material[specularIndex+1] * pow;
		    ib += Ids[2] * material[specularIndex+2] * pow;
		}
		
		//System.out.println(ir+" "+ig+" "+ib);
		
		if (ir > 1)
			ir = 1.0f;
		if (ig > 1)
			ig = 1.0f;
		if (ib > 1)
			ib = 1.0f;

		return new Color( (float) ir, (float) ig, (float) ib);
	}
    
	public static void main(String[] args) 
	{
		Raytracer05_ShadingAA_OBJ rt = new Raytracer05_ShadingAA_OBJ();
		
		//rt.doRayTrace();
	}
}
